//给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
//
//
//
// 示例 1：
//
//
//输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
//输出： True
//说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
//
// 示例 2:
//
//
//输入: nums = [1,2,3,4], k = 3
//输出: false
//
//
//
// 提示：
//
//
// 1 <= k <= len(nums) <= 16
// 0 < nums[i] < 10000
// 每个元素的频率在 [1,4] 范围内
//
// Related Topics 位运算 记忆化搜索 数组 动态规划 回溯 状态压缩 👍 606 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;

@SuppressWarnings("all")
//Java：划分为k个相等的子集
public class 划分为k个相等的子集 {
    public static void main(String[] args) {
        Solution solution = new 划分为k个相等的子集().new Solution();
        // TO TEST
        int[] nums = {4, 3, 2, 3, 5, 2, 1};
        solution.canPartitionKSubsets(nums, 4);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }

            if (sum % k != 0)
                return false;
            int avg = sum / k;

            boolean[][] dp = new boolean[k + 1][1 << nums.length];
            dp[0][0] = true;

            ArrayList<Integer> stats = new ArrayList<>();

            for (int i = 0; i < 1 << nums.length; i++) {
                int s = 0;
                for (int j = 0; j < nums.length; j++) {
                    if ((i >> j & 1) == 1) {
                        s += nums[j];
                    }
                }
                if (s == avg)
                    stats.add(i);
            }


            for (int i = 1, j; i <= k; i++) {

                for (int stat : stats) {
                    for (j = 0; j < 1 << nums.length; j++) {
                        if ((stat & j) == 0 && dp[i - 1][j])
                            dp[i][stat | j] = dp[i - 1][j] | dp[i][stat | j];
                    }
                }
            }

            return dp[k][(1 << nums.length) - 1];

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
